The Probabilistic Simple Temporal Network with Uncertainty (PSTNU) is a variant of the Simple Temporal Network with Uncertainty (STNU) in which known probability distributions govern the timing of uncontrollable timepoints. Previous approaches to solving PSTNUs focus mininizing risk, that is, the probability of violating constraints. These approaches are not applicable in over-constrained controllability problems, when it is certain that all constraints can’t be satisfied. We introduce the Weighted Probabilistic Simple Temporal Network with Uncertainty (WPSTNU), which extends the PSTNU by attaching a fixed value to the satisfaction of temporal constraints, and allows the schedule to violate some constraints in order to maximize the expected value of satisfying others. We study the problem of Expected Value Strong Controllability (EvSC) of WPSTNUs, which seeks a fixed-time schedule maximizing the expected value of satisfied constraints. We solve the EvSC problem using a mixed integer linear program (MILP) that bounds below the probability of satisfying constraints involving uncontrollable timepoints. While solving MILPs generally takes exponential time, we demonstrate our formulation’s effective performance using scheduling problems derived from the HEATlab and MIT ROVERS data sets. We then show how to use this MILP to reschedule during execution, after time has passed and uncertainty is reduced. We describe different fixed-period rescheduling approaches, including time-based and event-based, and report on the most successful strategies compared to the expected value of the fixed schedule produced by the MILP. All of our methods are evaluated on problems with both symmetric and asymmetric (skewed) probability distributions. We show that periodically rescheduling improves the expected value when compared to the fixed schedule, and describe how the benchmark and skewness impact the schedule value improvement. The resulting analysis shows that solving EvSC problems on WPSTNUs is a viable alternative to solving over-constrained controllability problems.

Scheduling in the presence of uncertainty is an area of interest in artificial intelligence due to the large number of applications. We study the problem of dynamic controllability (DC) of disjunctive temporal networks with uncertainty (DTNU), which seeks a strategy to satisfy all constraints in response to uncontrollable action durations. We introduce a more restricted, stronger form of controllability than DC for DTNUs, time-based dynamic controllability (TDC), and present a tree search approach to determine whether or not a DTNU is TDC. Moreover, we leverage the learning capability of a message passing neural network (MPNN) as a heuristic for tree search guidance. Finally, we conduct experiments for which the tree search shows superior results to state-of-the-art timed-game automata (TGA) based approaches. We observe that using an MPNN for tree search guidance leads to a significant increase in solving performance and scalability to harder DTNU problems.